﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using UnityEngine;

namespace Assets.Scripts.LDS
{
    class SceneSemGraph : SemanticGraph
    {

        public MetaScene m_graphMetaScene = new MetaScene(); // meta scene corresponding to the scene graph
        public Dictionary<int, int> m_graphNodeToModelListIdMap = new Dictionary<int, int>();

        // for matching
        public Dictionary<int, int> m_dbNodeToSubNodeMap = new Dictionary<int, int>();

        // support hierarchy
        public Dictionary<int, int> m_parentOfModel = new Dictionary<int, int>();  //  map to modelId of current model's parent
        public Dictionary<int, List<int>> m_childListOfModel = new Dictionary<int, List<int>>();  // map to modelIds of current model's children
        public List<List<int>> m_levelOfObjs = new List<List<int>>();  // map to modelIds of objs in different support levels

        public bool m_allSynthNodesInited;
        public int m_modelNum;

        public int m_dbSSGId;  // id of matched dbSSG
        public SemanticGraph m_alignedQuerySSG;

        public List<int> m_addedContextNodeIds = new List<int>();


        private String m_fullFilename;

        /*----------TSScene Code-----------*/
        public bool m_isLoadFromFile;

        int m_previewId;
        /*--------------------*/

        public SceneSemGraph()
        {
            m_allSynthNodesInited = false;
            m_dbSSGId = -1;
            m_alignedQuerySSG = null;
        }
        public SceneSemGraph(String s)
        {
            m_fullFilename = s;
            loadGraph(m_fullFilename);
            m_allSynthNodesInited = false;
            m_dbSSGId = -1;
            m_alignedQuerySSG = null;
        }
        public SceneSemGraph(SceneSemGraph sg)
        {

            m_graphMetaScene = new MetaScene(sg.m_graphMetaScene);
            m_graphNodeToModelListIdMap = new Dictionary<int, int>(sg.m_graphNodeToModelListIdMap);
            m_modelNum = sg.m_modelNum;
            m_nodeNum = sg.m_nodeNum;
            m_edgeNum = sg.m_edgeNum;

            m_nodes = Util.CopyList<SemNode>(sg.m_nodes);
            m_edges = Util.CopyList<SemEdge>(sg.m_edges);

            m_allSynthNodesInited = false;
            m_dbSSGId = sg.m_dbSSGId;

            if (m_alignedQuerySSG == null)
            {
                m_alignedQuerySSG = null;
            }
            else m_alignedQuerySSG = new SemanticGraph(sg.m_alignedQuerySSG);

            m_addedContextNodeIds = new List<int>(sg.m_addedContextNodeIds);

            // for matching
            m_dbNodeToSubNodeMap = new Dictionary<int, int>(sg.m_dbNodeToSubNodeMap);

            // support hierarchy
            m_parentOfModel = new Dictionary<int, int>(sg.m_parentOfModel);  //  map to modelId of current model's parent
            m_childListOfModel = new Dictionary<int, List<int>>(sg.m_childListOfModel);  // map to modelIds of current model's children
            m_levelOfObjs = new List<List<int>>(m_levelOfObjs);  // map to modelIds of objs in different support levels

            m_isLoadFromFile = sg.m_isLoadFromFile;

            m_fullFilename = sg.m_fullFilename;

            /*----------TSScene Code-----------*/
            m_previewId = sg.m_previewId;

        }
        // generate a copy of sg


        public MetaScene getMetaScene()
        {
            return m_graphMetaScene;
        }

        public void covertToTSScene()
        {
            m_modelNum = m_graphMetaScene.m_metaModellList.Count;

            //buildSupportHierarchy();
        }

        //public void initMetaModelSuppPlanes(unordered_map<string, Model*> models);


        public void loadGraph(String filename)
        {
            m_fullFilename = filename;
            StreamReader ifs;

            if (!File.Exists(@filename))
            {
                TextDialog.textDebug("\nTextSemGraphManager: cannot open SEL output file\n");
                return;
            }
            ifs = File.OpenText(@filename);

            m_graphMetaScene.m_sceneFileName = System.IO.Path.GetFileNameWithoutExtension(filename);   // scene_01.txt

            m_graphMetaScene.m_sceneFormat = ifs.ReadLine();

            // set DB path for the SSG
            if (m_graphMetaScene.m_sceneFormat == "StanfordSceneDatabase" || m_graphMetaScene.m_sceneFormat == "SceneNNConversionOutput")
            {
                m_graphMetaScene.m_sceneDBPath = Params.localSceneDBDirectory;
                m_graphMetaScene.m_sceneFilePath = m_graphMetaScene.m_sceneDBPath + "/scenes";
                m_graphMetaScene.m_modelRepository = m_graphMetaScene.m_sceneDBPath + "/models";
            }

            int currModelID = -1;
            string currLine = "";
            while (ifs.Peek() >= 0 && !currLine.Contains("nodeNum"))
            {
                currLine = ifs.ReadLine();

                //	load model info
                if (currLine.Contains("modelCount "))
                {
                    m_modelNum = Util.StringToIntegerList(currLine, "modelCount ")[0];
                    m_graphMetaScene.m_metaModellList = new List<MetaModel>();
                    for (int _tmp = 0; _tmp < m_modelNum; _tmp++)
                    {
                        m_graphMetaScene.m_metaModellList.Add(new MetaModel());
                    }
                }

                if (currLine.Contains("newModel "))
                {
                    currModelID++;

                    List<String> parts = Util.PartitionString(currLine, " ");
                    int modelIndex = Util.StringToInt(parts[1]);


                    m_graphMetaScene.m_metaModellList[currModelID].id = modelIndex;
                    m_graphMetaScene.m_metaModellList[currModelID].name = parts[2];
                    m_graphMetaScene.m_metaModellList[currModelID].path = m_graphMetaScene.m_modelRepository + "/" + parts[2] + ".obj";
                }

                if (currLine.Contains("transform "))
                {
                    List<float> transformVec = Util.StringToFloatList(currLine, "transform ");
                    Vector4 v1 = new Vector4(transformVec[0], transformVec[1], transformVec[2], transformVec[3]);
                    Vector4 v2 = new Vector4(transformVec[4], transformVec[5], transformVec[6], transformVec[7]);
                    Vector4 v3 = new Vector4(transformVec[8], transformVec[9], transformVec[10], transformVec[11]);
                    Vector4 v4 = new Vector4(transformVec[12], transformVec[13], transformVec[14], transformVec[15]);// transformation vector in stanford scene file is column-wise
                    Matrix4x4 transMat = new Matrix4x4(v1, v2, v3, v4);
                    m_graphMetaScene.m_metaModellList[currModelID].transformation = transMat;
                }
                
                if (currLine.Contains("position "))
                {
                    // position saves models init position before transformed
                    List<float> elementList = Util.StringToFloatList(currLine, "position ");
                    m_graphMetaScene.m_metaModellList[currModelID].position = new Vector3(elementList[0], elementList[1], elementList[2]);
                }

                if (currLine.Contains("frontDir "))
                {
                    // position saves model OBB bottom center which is already transformed
                    List<int> dirElementList = Util.StringToIntegerList(currLine, "frontDir ");
                    Vector3 initFrontDir = new Vector3(dirElementList[0], dirElementList[1], dirElementList[2]);
                    m_graphMetaScene.m_metaModellList[currModelID].frontDir = Util.TransformVector(m_graphMetaScene.m_metaModellList[currModelID].transformation, initFrontDir);
                    m_graphMetaScene.m_metaModellList[currModelID].frontDir.Normalize();
                }

                if (currLine.Contains("upDir "))
                {
                    // upDir saves models init upDir before transformed
                    List<int> dirElementList = Util.StringToIntegerList(currLine, "upDir ");
                    Vector3 initUpDir = new Vector3(dirElementList[0], dirElementList[1], dirElementList[2]);
                    m_graphMetaScene.m_metaModellList[currModelID].upDir = Util.TransformVector(m_graphMetaScene.m_metaModellList[currModelID].transformation, initUpDir);
                    m_graphMetaScene.m_metaModellList[currModelID].upDir.Normalize();
                }

                if (currLine.Contains("bbTopPlane "))
                {
                    continue;
                    // bbTopPlane won't be used in matching

                    // for bbTopPlane plane, the data saved in ssg is already transformed
                    List<float> floatElementList = Util.StringToFloatList(currLine, "bbTopPlane ");
                    List<Vector3> corners = new List<Vector3>();
                    for (int v = 0; v < 4; v++)
                    {
                        corners.Add(new Vector3(floatElementList[3 * v], floatElementList[3 * v + 1], floatElementList[3 * v + 2]));
                    }

                    //m_graphMetaScene.m_metaModellList[currModelID].bbTopPlane = new SuppPlane(corners);
                    //m_graphMetaScene.m_metaModellList[currModelID].bbTopPlane.m_sceneMetric = 0.0254;
                }


                if (currLine.Contains("parentPlaneUVH "))
                {
                    List<float> floatElementList = Util.StringToFloatList(currLine, "parentPlaneUVH ");
                    Vector3 uvh = new Vector3(floatElementList[0], floatElementList[1], floatElementList[2]);

                    m_graphMetaScene.m_metaModellList[currModelID].parentPlaneUVH = uvh;
                }
            }

            //	load nodes
            int metaModelId = 0;
            if (currLine.Contains("nodeNum "))
            {
                int nodeNum = Util.StringToIntegerList(currLine, "nodeNum ")[0];
                for (int i = 0; i < nodeNum; i++)
                {
                    currLine = ifs.ReadLine();
                    List<string> parts = Util.PartitionString(currLine, ",");

                    // object node
                    if (parts[1] == "object")
                    {
                        if (parts.Count > 2)
                        {
                            addNode((parts[1]), (parts[2]));

                            // set model catgory in meta model
                            m_graphMetaScene.m_metaModellList[metaModelId].catName = (parts[2]);
                        }
                        else
                        {
                            addNode((parts[1]), "noname");
                        }

                        m_graphNodeToModelListIdMap[m_nodeNum - 1] = metaModelId;
                        metaModelId++;
                    }
                    else
                    {
                        addNode((parts[1]), (parts[2]));
                    }
                }
            }

            currLine = ifs.ReadLine();

            // load edges
            if (currLine.Contains("edgeNum "))
            {
                int edgeNum = Util.StringToIntegerList(currLine, "edgeNum ")[0];
                for (int i = 0; i < edgeNum; i++)
                {
                    currLine = ifs.ReadLine();
                    List<int> parts = Util.StringToIntegerList(currLine, "", ",");
                    addEdge(parts[1], parts[2]);
                }
            }

            parseNodeNeighbors();

            ifs.Close();
        }

        public void saveGraph(string file_path)
        {
            using(StreamWriter ofs = new StreamWriter(@file_path))
            {
                ofs.Write("StanfordSceneDatabase\n");

                // save scene meta data
                int modelNum = m_graphMetaScene.m_metaModellList.Count;
                ofs.Write("modelCount " + modelNum + "\n");

                for (int i = 0; i < modelNum; i++)
                {
                    MetaModel md = m_graphMetaScene.m_metaModellList[i];
                    ofs.WriteLine("newModel " + i + " " + md.name);
                    ofs.WriteLine("transform " + string.Format("{0:F6}", md.transformation.m00) + " " + string.Format("{0:F6}", md.transformation.m10) + " " + string.Format("{0:F6}", md.transformation.m20) + " " + string.Format("{0:F6}", md.transformation.m30) + " "
                        + string.Format("{0:F6}", md.transformation.m01) + " " + string.Format("{0:F6}", md.transformation.m11) + " " + string.Format("{0:F6}", md.transformation.m21) + " " + string.Format("{0:F6}", md.transformation.m31) + " "
                        + string.Format("{0:F6}", md.transformation.m02) + " " + string.Format("{0:F6}", md.transformation.m12) + " " + string.Format("{0:F6}", md.transformation.m22) + " " + string.Format("{0:F6}", md.transformation.m32) + " "
                        + string.Format("{0:F6}", md.transformation.m03) + " " + string.Format("{0:F6}", md.transformation.m13) + " " + string.Format("{0:F6}", md.transformation.m23) + " " + string.Format("{0:F6}", md.transformation.m33) + " ");

                    /*

                    // position saves model OBB bottom center which is already transformed
                    ofs.Write("position " + md.position.x + " " + md.position.y + " " + md.position.z + "\n");

                    // frontDir saves models init upDir frontDir transformed
                    Matrix4x4 invTrans = md.transformation.inverse;
                    Vector3 initFrontDir = Util.TransformVector(invTrans, md.frontDir);
                    initFrontDir.Normalize();
                    ofs.Write("frontDir " + initFrontDir.x + " " + initFrontDir.y + " " + initFrontDir.z + "\n");

                    // upDir saves models init upDir before transformed
                    Vector3 initUpDir = Util.TransformVector(invTrans, md.upDir);
                    initUpDir.Normalize();
                    ofs.Write("upDir " + initUpDir.x + " " + initUpDir.y + " " + initUpDir.z + "\n");

                    // for support plane, the data saved in ssg is already transformed
                    //ofs.Write("bbTopPlane " + md.bbTopPlane.m_corners[0].x + " " + md.bbTopPlane.m_corners[0].y + " " + md.bbTopPlane.m_corners[0].z + " "
                    //    + md.bbTopPlane.m_corners[1].x + " " + md.bbTopPlane.m_corners[1].y + " " + md.bbTopPlane.m_corners[1].z + " "
                    //    + md.bbTopPlane.m_corners[2].x + " " + md.bbTopPlane.m_corners[2].y + " " + md.bbTopPlane.m_corners[2].z + " "
                    //    + md.bbTopPlane.m_corners[3].x + " " + md.bbTopPlane.m_corners[3].y + " " + md.bbTopPlane.m_corners[3].z + "\n");
                    ofs.Write("parentPlaneUVH " + md.parentPlaneUVH.x + " " + md.parentPlaneUVH.y + " " + md.parentPlaneUVH.z + "\n");
                    */
                }

                // save nodes in format: nodeId,nodeType,nodeName,inEdgeNodeList,outEdgeNodeList
                ofs.Write("nodeNum " + m_nodeNum + "\n");
                for (int i = 0; i < m_nodeNum; i++)
                {
                    ofs.Write(i + "," + m_nodes[i].nodeType + "," + m_nodes[i].nodeName + ","
                        + Util.GetIntString(m_nodes[i].inEdgeNodeList, " ") + ","
                        + Util.GetIntString(m_nodes[i].outEdgeNodeList, " ") + "\n");
                }

                // save edges in format: edgeId,startId endId
                ofs.Write("edgeNum " + m_edgeNum + "\n");
                for (int i = 0; i < m_edgeNum; i++)
                {
                    ofs.Write(i + "," + m_edges[i].sourceNodeId + "," + m_edges[i].targetNodeId + "\n");
                }
                TextDialog.textDebug("SceneSemGraph: graph saved.\n");
            }
        }


        public SceneSemGraph getSubGraph(List<int> nodeList)
        {
            SceneSemGraph subGraph = new SceneSemGraph();

            List<int> objNodeList = new List<int>();

            m_dbNodeToSubNodeMap.Clear();

            // build graph nodes
            int currSubSSGNodeNum = 0;
            for (int i = 0; i < nodeList.Count; i++)
            {
                int dbNodeId = nodeList[i];
                m_dbNodeToSubNodeMap[dbNodeId] = currSubSSGNodeNum;

                SemNode dbNode = m_nodes[dbNodeId];
                subGraph.addNode(dbNode);
                currSubSSGNodeNum++;

                if (dbNode.nodeType == "object")
                {
                    objNodeList.Add(dbNodeId);
                }
            }

            // build graph edges
            for (int i = 0; i < m_edgeNum; i++)
            {
                SemEdge dbEdge = m_edges[i];

                if (m_dbNodeToSubNodeMap.ContainsKey(dbEdge.sourceNodeId)
                    && m_dbNodeToSubNodeMap.ContainsKey(dbEdge.targetNodeId))
                {
                    int newSourceId = m_dbNodeToSubNodeMap[dbEdge.sourceNodeId];
                    int newTargetId = m_dbNodeToSubNodeMap[dbEdge.targetNodeId];
                    subGraph.addEdge(newSourceId, newTargetId);
                }
            }

            // set meta scene
            int modelInSceneId = 0;
            for (int i = 0; i < objNodeList.Count; i++)
            {
                int dbNodeId = objNodeList[i];

                // non-object node is not saved in the map
                if (m_graphNodeToModelListIdMap.ContainsKey(dbNodeId))
                {
                    int dbMetaModelId = m_graphNodeToModelListIdMap[dbNodeId];

                    if (dbMetaModelId < m_modelNum)
                    {
                        MetaModel dbMd = m_graphMetaScene.m_metaModellList[dbMetaModelId];
                        dbMd.isSelected = Convert.ToInt32(m_nodes[dbNodeId].isAnnotated);

                        subGraph.m_graphMetaScene.m_metaModellList.Add(dbMd);
                        int currNodeId = m_dbNodeToSubNodeMap[dbNodeId];
                        subGraph.m_graphNodeToModelListIdMap[currNodeId] = modelInSceneId;
                        modelInSceneId++;
                    }
                }
            }

            subGraph.m_graphMetaScene.m_sceneFileName = m_graphMetaScene.m_sceneFileName;

            subGraph.parseNodeNeighbors();

            return subGraph;
        }
        public void restoreMissingSupportRelationNodes()
        {
            for (int i = 0; i < m_nodes.Count; i++)
            {
                SemNode relNode = m_nodes[i];

                // onleft, onright, oncenter
                if (relNode.nodeType == "pair_relation" &&
                    relNode.nodeName.Contains("on") && !relNode.nodeName.Contains("front"))
                {
                    int actNodeId = relNode.inEdgeNodeList[0];
                    if (!hasSupportNode(actNodeId))
                    {
                        int anchorNodeId = relNode.outEdgeNodeList[0];
                        addNode(SSGNodeType[(int)SemNode.NodeType.Pair], "vertsupport");
                        int currNodeId = m_nodeNum - 1;

                        addEdge(actNodeId, currNodeId);
                        addEdge(currNodeId, anchorNodeId);
                    }
                }
            }

            for (int i = 0; i < m_nodes.Count; i++)
            {
                SemNode currNode = m_nodes[i];

                if (currNode.nodeType == "object")
                {
                    int actParentNodeId = findParentNodeIdForNode(i);
                    // try to find potential node in current scene
                    if (actParentNodeId == -1)
                    {
                        actParentNodeId = findPotentialParentNodeIdForNode(i);
                        if (actParentNodeId != -1)
                        {
                            addNode(SSGNodeType[(int)SemNode.NodeType.Pair], "vertsupport");
                            int currNodeId = m_nodeNum - 1;

                            addEdge(i, currNodeId);
                            addEdge(currNodeId, actParentNodeId);
                        }
                    }
                }
            }
        }
        public bool hasSupportNode(int actNodeId)
        {
            SemNode actNode = m_nodes[actNodeId];

            for (int i = 0; i < actNode.outEdgeNodeList.Count; i++)
            {
                int relNodeId = actNode.outEdgeNodeList[i];
                SemNode relNode = m_nodes[relNodeId];

                if (relNode.nodeName.Contains("support"))
                {
                    return true;
                }
            }

            return false;
        }

        public void mergeWithMatchedSSG(SceneSemGraph matchedSg)
        {
            // insert nodes and edges
            this.mergeWithGraph(matchedSg);
            insertUnAlignedObjsFromGraph(matchedSg);
        }// update current USserSSG with retrieved subSSG
        public void insertUnAlignedObjsFromGraph(SceneSemGraph matchedSg)
        {
            // insert unaligned objects to meta model list
            for (int mi = 0; mi < matchedSg.m_nodeNum; mi++)
            {
                SemNode matchedSgNode = matchedSg.m_nodes[mi];
                if (!matchedSgNode.isAligned && matchedSgNode.nodeType == "object" && matchedSg.m_graphNodeToModelListIdMap.ContainsKey(mi))
                {
                    int mModelId = matchedSg.m_graphNodeToModelListIdMap[mi];
                    MetaModel modelToInsert = matchedSg.m_graphMetaScene.m_metaModellList[mModelId];
                    this.m_graphMetaScene.m_metaModellList.Add(modelToInsert);

                    int currMetaModelNum = this.m_graphMetaScene.m_metaModellList.Count;
                    int ci = matchedSg.m_nodeAlignMap[mi];
                    this.m_graphNodeToModelListIdMap[ci] = currMetaModelNum - 1;
                }
            }

            m_modelNum = m_graphMetaScene.m_metaModellList.Count;
        }

        public bool findRefNodeForRelationNode(SemNode sgNode, ref int refNodeId, ref int activeNodeId)
        {
            //edge dir: (active, relation), (relation, reference)
            int actNodeId = sgNode.activeNodeList[0];  // active
            int anchorNodeId = sgNode.anchorNodeList[0]; // reference


            // find the reference node
            if (this.m_nodes[actNodeId].isAligned && !this.m_nodes[anchorNodeId].isAligned)
            {
                refNodeId = actNodeId;
                activeNodeId = anchorNodeId;

                return true;
            }
            else if (this.m_nodes[anchorNodeId].isAligned && !this.m_nodes[actNodeId].isAligned)
            {
                refNodeId = anchorNodeId;
                activeNodeId = actNodeId;

                return true;
            }
            // if no reference node is aligned, just use the ref node in matchedSg, and align to it
            else
            {
                return false;
            }
        }
        public int findParentNodeIdForModel(int modelId)
        {
            int currNodeId = getNodeIdWithModelId(modelId);
            return findParentNodeIdForNode(currNodeId);
        }
        public int findParentNodeIdForNode(int currNodeId)
        {
            if (currNodeId == -1)
            {
                return -1;
            }

            String currNodeName = m_nodes[currNodeId].nodeName;
            if (currNodeName == "chair" || currNodeName == "desk" || currNodeName == "table"
                || currNodeName.Contains("cabinet") || currNodeName.Contains("couch")
                || currNodeName.Contains("shelf"))
            {
                return -1;
            }

            if (m_nodes[currNodeId].outEdgeNodeList.Count == 0)
            {
                return -1;
            }
            else
            {
                for (int i = 0; i < m_nodes[currNodeId].outEdgeNodeList.Count; i++)
                {
                    int relationNodeId = m_nodes[currNodeId].outEdgeNodeList[i]; // monitor . on
                    SemNode relNode = m_nodes[relationNodeId];
                    if (m_nodes[relationNodeId].outEdgeNodeList.Count != 0 && relNode.nodeName.Contains("support"))
                    {
                        int refNodeId = m_nodes[relationNodeId].outEdgeNodeList[0]; // on . desk
                        return refNodeId;
                    }
                }
                return -1;
            }
        }
        public int findPotentialParentNodeIdForNode(int nodeId)
        {
            String currNodeName = m_nodes[nodeId].nodeName;

            for (int i = 0; i < m_nodes.Count; i++)
            {
                SemNode sgNode = m_nodes[i];

                if ((currNodeName == "knife" || currNodeName == "fork" || currNodeName == "plate")
                    && sgNode.nodeName == "table")
                {
                    return i;
                }

                if ((currNodeName == "speaker" || currNodeName == "monitor")
                    && (sgNode.nodeName == "desk"))
                {
                    return i;
                }
            }

            return -1;
        }

        public int getNodeIdWithModelId(int modelId)
        {
            int currNodeId = -1;

            // find graph node id w.r.t to the model id
            foreach (var iter in m_graphNodeToModelListIdMap)
            {
                if (iter.Value == modelId && iter.Key != -1)
                {
                    currNodeId = iter.Key;
                    break;
                }
            }

            return currNodeId;
        }
        public MetaModel getModelWithNodeId(int nodeId)
        {
            int modelId = m_graphNodeToModelListIdMap[nodeId];
            return m_graphMetaScene.m_metaModellList[modelId];
        }

        public void buildSupportHierarchy()
        {
            m_levelOfObjs.Clear();
            m_parentOfModel.Clear();
            m_childListOfModel.Clear();

            List<int> isNodeProcessed = new List<int>();
            for (int i = 0; i < m_nodes.Count; i++)
            {
                isNodeProcessed.Add(0);

            }
            List<int> newLevelOfObjIds = new List<int>();

            for (int i = 0; i < m_nodes.Count; i++)
            {
                SemNode sgNode = m_nodes[i];

                if (sgNode.nodeType == "object" && isBaseLevelObj(i))
                {
                    int modelId = m_graphNodeToModelListIdMap[i];
                    newLevelOfObjIds.Add(modelId);

                    m_parentOfModel[modelId] = -1;
                    isNodeProcessed[i] = 1;
                }
            }

            m_levelOfObjs.Add(newLevelOfObjIds);

            if (m_modelNum == 1) return;

            int passNum = 3;
            for (int p = 0; p < passNum; p++)
            {
                List<int> lastLevelOfObjIds = new List<int>(m_levelOfObjs.Last());

                newLevelOfObjIds = new List<int>();

                for (int ni = 0; ni < m_nodes.Count; ni++)
                {
                    SemNode sgNode = m_nodes[ni];

                    if (sgNode.nodeType == "object" && !Convert.ToBoolean(isNodeProcessed[ni]))
                    {
                        int modelId = m_graphNodeToModelListIdMap[ni];

                        // find relation node
                        for (int ri = 0; ri < sgNode.outEdgeNodeList.Count; ri++)
                        {
                            int relationNodeId = sgNode.outEdgeNodeList[ri];
                            SemNode relNode = m_nodes[relationNodeId];

                            // find anchor obj
                            if (relNode.nodeName.Contains("support"))
                            {
                                int anchorNodeId = relNode.anchorNodeList[0];
                                int anchorModelId = m_graphNodeToModelListIdMap[anchorNodeId];

                                if (lastLevelOfObjIds.Contains(anchorModelId))
                                {
                                    newLevelOfObjIds.Add(modelId);
                                    m_parentOfModel[modelId] = anchorModelId;
                                    //m_childListOfModel[anchorModelId].Add(modelId);
                                    isNodeProcessed[ni] = 1;
                                }
                            }
                        }
                    }
                }

                if (newLevelOfObjIds.Count != 0)
                {
                    m_levelOfObjs.Add(newLevelOfObjIds);
                }
            }

            // collect the remaining objs if there is any
            newLevelOfObjIds.Clear();
            for (int ni = 0; ni < m_nodes.Count; ni++)
            {
                SemNode sgNode = m_nodes[ni];

                if (sgNode.nodeType == "object" && isNodeProcessed[ni] == 0)
                {
                    int modelId = m_graphNodeToModelListIdMap[ni];
                    newLevelOfObjIds.Add(modelId);
                }
            }

            if (newLevelOfObjIds.Count != 0)
            {
                m_levelOfObjs.Add(newLevelOfObjIds);
            }
        }
        public bool isBaseLevelObj(int nodeId)
        {
            String objName = m_nodes[nodeId].nodeName;

            SemNode sgNode = m_nodes[nodeId];

            // if no support rel node exist
            if (sgNode.outEdgeNodeList.Count == 0)
            {
                return true;
            }
            else
            {
                for (int i = 0; i < sgNode.outEdgeNodeList.Count; i++)
                {
                    int relationNodeId = sgNode.outEdgeNodeList[i];
                    SemNode relNode = m_nodes[relationNodeId];

                    if (relNode.nodeName.Contains("support"))
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        public List<int> findExistingInstanceIds(String catName)
        {
            List<int> ids = new List<int>();
            for (int i = 0; i < m_graphMetaScene.m_metaModellList.Count; i++)
            {
                MetaModel md = m_graphMetaScene.m_metaModellList[i];

                if ((md.catName) == catName)
                {
                    ids.Add(i);
                }
            }

            return ids;
        }
        public bool hasObj(String catName, int initModelNum = 0)
        {
            if (initModelNum == 0)
            {
                initModelNum = m_graphMetaScene.m_metaModellList.Count;
            }

            for (int i = 0; i < initModelNum; i++)
            {
                MetaModel md = m_graphMetaScene.m_metaModellList[i];

                if ((md.catName) == catName)
                {
                    return true;
                }
            }
            return false;
        }


        /// <summary>
        /// delete the first node which name is objectName, and delete the relation/attri node and edge about it
        /// </summary>
        /// <param name="objectName"></param>
        /// <returns></returns>
        public bool deleteObject(string objectName)
        {
            List<int> remove_objId = new List<int>();

            foreach (SemNode rt_node in m_nodes)
                if (rt_node.nodeName == objectName)
                {
                    // just delete the first node named objectName

                    // The Graph satisfies patterns below:
                    // object <- relation <- object
                    // object <- attr

                    remove_objId.Add(rt_node.nodeId);

                    List<SemEdge> remove_edges = new List<SemEdge>();
                    List<SemNode> remove_nodes = new List<SemNode>();
                    List<MetaModel> remove_metaModels = new List<MetaModel>();
                    Queue<SemNode> queue = new Queue<SemNode>();

                    //BFS find the node and edge need to delete
                    queue.Enqueue(rt_node);
                    remove_metaModels.Add(m_graphMetaScene.m_metaModellList[rt_node.nodeId]);

                    while (queue.Count > 0)
                    {
                        SemNode node = queue.Dequeue();
                        remove_nodes.Add(node);

                        foreach (int i in node.inEdgeNodeList)
                        {
                            if (m_nodes[i].nodeType != "object")
                                queue.Enqueue(m_nodes[i]);
                        }

                        foreach (int i in node.outEdgeNodeList)
                        {
                            if (m_nodes[i].nodeType != "object")
                                queue.Enqueue(m_nodes[i]);
                        }
                    }

                    foreach (var edge in m_edges)
                    {
                        if (remove_nodes.Exists(
                            delegate (SemNode node) {
                                return (node.nodeId == edge.sourceNodeId) || (node.nodeId == edge.targetNodeId);
                            }))
                            remove_edges.Add(edge);
                    }

                    // remove
                    foreach (var edge in remove_edges) m_edges.Remove(edge);
                    foreach (var node in remove_nodes) m_nodes.Remove(node);
                    foreach (var metaModel in remove_metaModels) m_graphMetaScene.m_metaModellList.Remove(metaModel);

                    // rebuild the indexs
                    m_nodeNum = m_nodes.Count;
                    m_edgeNum = m_edges.Count;
                    m_modelNum = m_graphMetaScene.m_metaModellList.Count;
                    Dictionary<int, int> idsMap = new Dictionary<int, int>();
                    for (int i = 0; i < m_nodes.Count; ++i)
                    {
                        idsMap[m_nodes[i].nodeId] = i;
                        m_nodes[i].nodeId = i;
                        m_nodes[i].inEdgeNodeList.Clear();
                        m_nodes[i].outEdgeNodeList.Clear();
                    }
                    for (int i = 0; i < m_edges.Count; ++i)
                    {
                        m_edges[i].sourceNodeId = idsMap[m_edges[i].sourceNodeId];
                        m_edges[i].targetNodeId = idsMap[m_edges[i].targetNodeId];

                        int s = m_edges[i].sourceNodeId, t = m_edges[i].targetNodeId;
                        m_edges[i].edgeId = i;
                        m_nodes[s].outEdgeNodeList.Add(t);
                        m_nodes[t].inEdgeNodeList.Add(s);
                    }
                    for(int i = 0;i< m_graphMetaScene.m_metaModellList.Count; ++i)
                    {
                        var metaModel = m_graphMetaScene.m_metaModellList[i];
                        metaModel.id = i;
                        Debug.Assert(m_nodes[i].nodeType == "object");
                    }

                    parseNodeNeighbors();

                    return true;
                }

            return false;
        }

    }
}
